<?php
/**
 * User: LRZ
 * Date: 2020/2/28
 * Time: 10:52
 */

/**
 *  28.实现 strStr()
 *
 *  标签：双指针、字符串
 *
 *  实现 strStr() 函数。
 *  给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 *  示例 1:
 *      输入: haystack = "hello", needle = "ll"
 *      输出: 2
 *
 *  示例 2:
 *      输入: haystack = "aaaaa", needle = "bba"
 *      输出: -1
 *
 *  说明：
 *      当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 *      sunday算法参考：https://blog.csdn.net/fff058/article/details/52204233
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/implement-strstr
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$haystack = 'I am testing mySunday on sunday!';
$needle   = 'sunday';
$res      = strStrTest($haystack, $needle);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function strStrTest($haystack, $needle)
{
    if ($needle === '') {
        return 0;
    }

    $hSize = strlen($haystack); # 待匹配串长度
    $nSize = strlen($needle); # 模式串长度

    if ($nSize > $hSize) {
        return -1;
    }

    # 计算偏移表
    $shift = [];
    for ($i = 0; $i < $nSize; $i++) {
        $shift[$needle[$i]] = $nSize - $i;
    }

    $i = 0; # 偏移量
    while ($i + $nSize <= $hSize) {
        $nums = 0; # 当前匹配的模式串下标
        while ($haystack[$i + $nums] === $needle[$nums]) {
            $nums++;
            if ($nums === $nSize) {
                return $i;
            }
        }
        if (isset($shift[$haystack[$i + $nSize]])) { # 判断模式串后一位字符是否在模式串中
            # 对齐该字符
            $i += $shift[$haystack[$i + $nSize]];
        } else {
            # 直接滑动nSize位
            $i += $nSize;
        }
    }

    return -1;
}